/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        111.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/8 20:58
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
#include "../binary_tree/tree_node.h"
#include <queue>

using namespace std;

/*
 * 给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量
 */
class Solution {
public:
    int minDepth(TreeNode *root) {
        if (root == nullptr)
            return 0;
        int depth = 1;
        queue<TreeNode *> queue;
        queue.push(root);

        while (!queue.empty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                TreeNode *temp = queue.front();
                queue.pop();
                if (temp->left == nullptr && temp->right == nullptr) {
                    return depth;
                }
                if (temp->left != nullptr)
                    queue.push(temp->left);
                if (temp->right != nullptr)
                    queue.push(temp->right);
            }
            depth++;
        }
        return depth;
    }
};